package listnode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class _1019_链表中的下一个更大节点 {

    /**
     * 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
     * <p>
     * 每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且  node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
     * <p>
     * 返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
     * <p>
     * 注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
     * <p>
     * <p>
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/next-greater-node-in-linked-list
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param head
     * @return
     */
    public int[] nextLargerNodes(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        int[] r = new int[count];
        cur = head;
        for (int i = 0; i < r.length && cur != null; i++) {
            ListNode dummy = cur.next;
            while (dummy != null) {
                if (cur.val < dummy.val) {
                    r[i] = dummy.val;
                    break;
                }
                dummy = dummy.next;
            }
            cur = cur.next;
        }
        r[count - 1] = 0;
        return r;
    }

    public static int[] nextLargerNodes1(ListNode head) {
        List<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack();
        for (ListNode node = head; node != null; node = node.next) {
            while (!stack.isEmpty() && node.val > list.get(stack.peek())) {
                list.set(stack.pop(), node.val);
            }
            stack.push(list.size());
            list.add(node.val);
        }
        for (int i : stack) {
            list.set(i, 0);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(7);
        ListNode n3 = new ListNode(4);
        ListNode n4 = new ListNode(8);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        int[] ints = nextLargerNodes2(n1);

    }

    public static int[] nextLargerNodes2(ListNode head) {
        List<Integer> r = new ArrayList<>();
        Stack<Integer> index = new Stack<>();
        for(ListNode node = head; node!=null; node = node.next){
            while (!index.isEmpty() && node.val > r.get(index.peek())) {
                r.set(index.pop(), node.val);
            }
            index.push(r.size());
            r.add(node.val);
        }

        for (Integer integer : index) {
            r.set(integer,0);
        }
        int[] i = new int[r.size()];
        for (int j = 0; j < r.size(); j++) {
            i[j]= r.get(j);
        }
        return i;
    }

}
